The invention pertains to the field of videographic machines for computer-aided design and for simulation. More particularly, the invention pertains to the field of circuitry for use in performing Z-buffering, Gouraud shading, and texture mapping in such machines by calculation of the intersections between raster lines and polygon sides.
Z-buffering, Gouraud shading and texture mapping are features which are normally found on very expensive and complex graphics workstations since these features greatly improve the quality of the graphic presentation. Many graphics workstations which cost as much as $50,000 do not have Gouraud shading.
Gouraud shading, or intensity-interpolation shading, eliminates intensity discontinuities at edges and varies the intensity of the fill of a polygon thorughout thereby creating a smoother surface appearance. Typically in graphics machines, three-dimensional objects having curved surfaces are represented by a plurality of flat polygons which are joined at their boundaries to approximate the curved surface. In a machine which does not have Gouraud shading, each polygon will be shaded with an intensity which is calculated based upon the polygon's position and orientation in space relative to the light source. Where adjoining polygons have different orientations in space, the pixels in these polygons may have different intensities. The result is that the boundary between the two polygons becomes quite visible because of the difference in intensity of the pixels on either side of the boundary. This detracts from the graphic representation because such sudden changes in intensity are not normally seen on curved surfaces.
Machines that do not use Gouraud shading often use flat shading, which results in an even or equal intensity at all pixels on a scan line passing through a particular polygon. The technique of Gouraud shading tends to remove the edges on a curved surface comprised of polygons joined at a shallow angle by calculating normals for the vertices of polygons which are the average of the normals for all the polygons which are joined to form the vertices. This "vertex normal" is used only for intensity calculations, thereby making the intensity on the edges of the associated polygons blend on either side of the edges so as to effectively make the edges disappear or fade in significance.
The Gouraud shading process consists of four steps. First, surface normals are calculated for each polygon. Second, vertex normals (a line perpendicular to the edge which bisects the angle between the plane surfaces which define the edge) are calculated by averaging the surface normals of all polygon facets that share the vertex. If an edge is meant to be visible, such as at the joint between a plane's wing and body, then two vertex normals, one for each side of the edge, are found by separately averaging the normals of polygons on each side of the edge. Third, vertex intensities are found by using the vertex normals with any desired shading model. Finally, each polygon is shaded by linear interpolation of vertex intensities along each edge and then between edges along each scan line.
The interpolation along edges can easily be integrated with the scan line hidden surface algorithm. With each edge, the starting intensity and the change of intensity for each unit change in the Y direction is stored. Then the visible span of a scan line passing through a polygon is filled by interpolating the intensity values of the two edges that bound the span. This technique has a tendency to remove the faceted appearance of an object and make the surface look smooth.
Gouraud shading is, therefore, an alternative form of calculating the shading at each pixel on a polygon by calculating the intensities at the vertices or at specific points on the polygon and assuming that the intensity varies linearly between the calculated points. This allows the polygon to be painted much faster, since the intensity at each point does not need to be calculated other than by the aforementioned interpolation. This interpolation is the same sort of mathematical operation that must occur in texture mapping and in various other operations that must be performed in the video circuitry of a CAD machine.
Heretofore, Gouraud shading was done in software or with, very complicated discrete circuitry. Thus, there has arisen a need for a simple, integrated and inexpensive circuit for implementing Gouraud shading on graphic workstations that are less expensive. Preferably, this circuitry would be such that it would be identical with circuitry used for other functions such as texture mapping etc. so that a single integrated circuit design could be used to do many different functions that normally found in only much more expensive machines.
Texture mapping is the process of mapping a pattern or color or some other texture onto a polygon at fill time. Fill time is the time during which the various pixels of a graphic image to be displayed have the digital data representing those pixels loaded into a frame buffer. A frame buffer is a memory which stores video data in the form of digital numbers which are used to control circuitry which cause the intensity and color control circuitry of a raster-scanned video display circuit to properly drive a cathode ray tube so as to display the image.
Texture mapping on a raster scanned display, like Gouraud shading, requires interpolation. A raster--scanned display is comprised of a plurality of horizontal scan lines which are parallel and spaced close together and which define the tracks along which the electron beam or beams of a cathode ray tube sweep along the phosphor coated surface of the tube. The image on the screen is "painted" by electronically sweeping the electron beam or beams from one edge of the screen to the other with changing intensity which changes with changing position to cause various patterns of intensity of light to appear on the screen.
To illustrate the concept of texture mapping, assume that the image to be displayed is a simple square which is tilted in three-dimensional space at an angle such that the normal to the surface of the square polygon is at an angle to all three orthogonal axes of a cartesian coordinate system. Suppose also that a texture map comprising the face of Winston Churchill is to be painted within this tilted polygon. Suppose also that the polygon is to be rotated and translated through three-dimensional space with the face of Winston Churchill constantly painted thereon such that the resulting display looks like a portrait of Winston Churchill on a square canvas which is tumbling as it flies across the screen. Texture mapping is the process of mapping the raster lines that pass through the image of the polygon on the screen to a fictional raster line that passes through the texture map at some angle. The angle that this line makes through the texture map causes the raster line to be painted such that the canvas appears on the screen the same way the canvas would look if the screen were a window and the canvas was viewed in whatever orientation in space the canvas currently had. In other words, texture mapping is the process of causing the two-dimensional display to be painted in such a way that the face of Winston Churchill is seen as it would be seen by the observer of the display when looking at an actual portrait of Winston Churchill tumbling through space at the particular angle which the portrait assumes at the moment in question.
More precisely, texture mapping is the process of mapping a raster line through a polygon to a corresponding line through the texture map and then using the pixels in the texture map which appear on the mapped line to paint the pixels the correct color and intensity on the corresponding raster line which passes through the polygon. This is done for every raster line and every pixel in the polygon and is done for every orientation of the polygon in three-dimensional space as it is projected onto a two-dimensional plane for display. This allows a patterned array representing a digitized image of the texture map to be mapped onto either a planar or curved surface on an object to be displayed. Values from the pattern array are used to control the intensity of the pixels of the displayed surface so that the surface appears to have the same texture as the texture map.
Texture mapping is done in two steps. First, the texture mapping of the selected texture pattern onto the object surface is done. Then, 3-D to 2-D projection and clipping transformation mapping of the 3-D object onto the 2-D screen is done.
In the prior art, texture mapping has been done in software. Software is generally slower than hardware, and thus there has arisen a need for a hardware circuit to do texture mapping which is simple, fast and economical. Since texture mapping involves interpolation, preferably the circuitry to do texture mapping would be similar to the circuitry used for Gouraud shading to minimize the expense of such circuitry.
Z-buffering is a method of preventing the display of hidden edges and hidden polygons in a three-dimensional image which has been mapped onto a two-dimensional display. That is, polygons and edges which are deeper, in space, i.e., farther away from the viewpoint of the observer, may be obscured by other polygons which are closer to the observer and which lie in the line of sight from the viewpoint of the observer to the deeper polygon. When a three-dimensional object comprised of polygons which are joined to form the surface of the object has such an orientation, to display the edges and polygons which would normally be hidden on a two-dimensional graphics display causes confusion and unnecessary complexity. Z-buffering includes the process of sorting the polygons by depth and generation of an ordered list of polygons. This list of polygons is then examined on the fly and the depth of each pixel of each polygon is calculated at fill time for purposes of determining the final video data which will be placed in the frame buffer. Thus a polygon may be only partially obscured.
There are several ways of performing Z-buffering. One way is to fill the frame buffer with the pixels of a particular polygon at fill time for that polygon. Then, when another overlapping polygon is to have its pixels added to the frame buffer, a comparison is made on a pixel-by-pixel basis between the depth of each pixel in polygon 2 versus the depth of any pixel having the same x,y coordinate in polygon 1. If a pixel in the second polygon which overlaps a pixel in the first polygon has a Z depth which is closer to the eye of the observer than the Z depth of the corresponding overlapped pixel, then the pixel from polygon 1 is overwritten with the data representing the pixel from polygon 2 in the frame buffer. This is done on a pixel-by-pixel basis such that the Z depth of each pixel controls whether the pixel will be displayed.
The Z-buffering process can be carried out by interpolation. This is done by calculating the z coordinate of the pixels at each end of a raster scan line where it intersects the edges of a polygon. Then, the z depth of individual pixels along the raster scan line are calculated by interpolation between the z depths of the pixels at the intersections between the raster scan line and the edges of the polygon.
Thus a need has arisen for simple, economical circuit which can perform the mathematical calculations necessary for Gouraud shading, texture mapping and Z-buffering. Preferably, this circuit should be in integrated form such that multiple copies of it may be made for dedication to the performance of individual ones of the three functions identified above.